\chapter[uvod_cp]{Úvod do omezujících podmínek}
{\it \quotation{Constraint programming represents one of the closest
	approaches computer science has yet made to the Holy Grail of
		programming: the user states the problem, the computer
		solves it.}}\crlf
		\rightaligned{{\bf Eugene C. Freuder,
			\from[constraints-magazine], Duben 1997  }}\crlf


Programování s~omezujícími podmínkami (Constraint programming, CP) je nástrojem pro řešení kombinatorických (optimalizačních) úloh. Základem je vytvoření modelu problému, který se skládá z~proměnných
svázaných libovolnými {\it podmínkami}. Ve většině případů mají proměnné
		konečně velký obor hodnot(doménu), pak mluvíme o~CSP (Constraint satisfaction
		problem). Cílem CSP je najít takové
	ohodnocení proměnných, které splňuje všechny podmínky a navíc
	patří do oboru hodnot. 
	Rozšířením CSP o~hodnotící funkci (např. z~části o~rozvrhování \in[rozvrhovani-def]) se dostáváme k~CSOP (Constraint
			satisfaction optimisation problem), kde nás
	zajímá právě to \quotation{nejlepší} řešení. 
	
	Základní pojmy jsou
	shrnuty v~\cite[Bartak_Introduction_CP, CBS] a podrobně o~CP
	pojednává \cite[onlineGuide_CP].

Vlastnosti omezujících podmínek jsou:
\startitemize
	\item Vyjadřují částečnou informaci ($X>3$, hodnota $X$ není
			určena jednoznačně)
	\item Poskytují lokální pohled na celý model problému (svazují
			jen několik proměnných -- ne všechny najednou)
	\item Mohou být heterogenní (domény proměnných mohou být různé)
	\item Nejsou směrové ($X=Y+1$ lze použít pro výpočet $X$ i $Y$).
	\item Jsou deklarativní -- neurčují výpočtovou proceduru pro své
	splnění.
	\item Jsou aditivní -- pořadí podmínek nehraje roli. Důležitá je
	jejich konjunkce.
\stopitemize
CSP se dá reprezentovat pomocí hypergrafu, kde vrcholy značí proměnné a
hrany podmínky. Hypergraf se dá převést na graf a ten pak řešit pomocí
prohledávacích algoritmů.




	Základními stavebními kameny CP jsou konzistenční techniky (část
			\in[cp_constraintPropagation]) a prohledávací
	algoritmy (část \in[cp_algoritmy]).


\section[cp_constraintPropagation]{Konzistenční techniky}
Konzistenční techniky (algoritmy) se starají o~to, aby hodnoty všech
domén splňovaly všechny omezující podmínky. Pokud tomu tak není, aktivně
prořežou jednotlivé domény, aby předchozí tvrzení platilo. Tomuto
procesu se říká { \it propagace omezujících podmínek}.   


Propagace podmínek tedy pracuje tak, že každá podmínka má svoji filtrovací funkci, kterou dokáže prořezávat domény proměnných, které podmínka svazuje. 
Jakmile se jedna z~proměnných v~podmínce změní, pak se volá filtrovací funkce. Tím se zaručí konzistence CSP.
Propagaci podmínek ukazuje obrázek \in[fig:CP].
   Propagace podmínek redukuje domény proměnných
	    opakovaným voláním filtrovacích algoritmů. Tento proces se
	    provádí až do okamžiku dosažení tzv. \quotation{fix-point},
	    kdy je CSP {\it hranově} i {\it vrcholově konzistentní}.

\useexternalfigure[CP1][images/cp1.pdf][width=0.5\textwidth]
\useexternalfigure[CP2][images/cp2.pdf][width=0.5\textwidth]
\placefigure
  [here,force]
  [fig:CP]
  {Zadání problému a následná propagace podmínek.}
{\startcombination[2*1]
    {\externalfigure[CP1]}   {CSP reprezentovaný grafem obsahující proměnné s~jejich doménami a
  omezujícími podmínkami.}
    {\externalfigure[CP2]} {Propagace omezujících podmínek.}

  \stopcombination
}


\definedescription[definition][headstyle=bold,width=broad,location=hanging]
\definition{Vrcholová konzistence}
Vrchol reprezentující proměnnou $X$ je {\it vrcholově konzistentní (node consistent)}, právě když
každá hodnota z~aktuální domény $D_x$ splňuje všechny unární podmínky na $X$.\crlf
CSP je {\it vrcholově konzistentní} právě tehdy, když je každý vrchol
vrcholově konzistentní.\par


\definition{Hranová konzistence}
Hrana $(V_i,V_j)$ je {\it hranově konzistentní (arc consistent)}, právě
když pro každou hodnotu $x$ z~aktuální domény $D_i$ existuje hodnota $y$
v~aktuální doméně $D_j$ tak, že ohodnocení  $V_i =x \mbox{ a } V_j=y$
splňuje všechny binární podmínky nad $V_i \mbox{, } V_j$. \crlf
CSP je {\it hranově konzistentní}, právě když je každá jeho hrana
$(V_i,V_j)$ hranově konzistentní (v~obou směrech).\par



\useexternalfigure[nonAC][images/nonArcConsistency.pdf][width=0.4\textwidth]
\useexternalfigure[AC][images/ArcConsistency.pdf][width=0.4\textwidth]
\placefigure
  [here,force]
  [fig:arcConsistency]
  {Hranově nekonzistentní a konzistentní CSP}
{\startcombination[2*1]
    {\externalfigure[nonAC]}   {Hranově nekonzistentní (existuje hodnota v~$A$
		    i $B$, která nesplňuje podmínku)}
    {\externalfigure[AC]} {Hranově konzistentní (všechny hodnoty v~$A$ i $B$
		    splňují podmínky.}
  \stopcombination
}






\section[cp_algoritmy]{Prohledávací algoritmy}
V~této části budou rozebrány 3 hlavní prohledávací algoritmy, které nabízí
knihovna Gecode, kterou budeme v~naší práci používat a bude jí věnována
část \in[cp_gecode].
O~informovaných i neinformovaných algoritmech prohledávání pojednává \cite[UI1,Russell03].

\subsection[cp_dfs]{Depth first search (DFS)}
DFS (slepé prohledávání do hloubky) patří mezi neinformované metody
prohledávání.
Algoritmus pracuje se seznamy otevřených a prošlých vrcholů.
Prohledávání začíná expanzí kořene a umístěním následníků na začátek seznamu
otevřených vrcholů. Pak se expanduje vždy první se seznamu otevřených
(jeho následníci se opět uloží na začátek seznamu otevřených) až
do okamžiku kdy je nalezeno řešení nebo je seznam otevřených vrcholů
prázdný (řešení nenalezeno). Obrázek \in[fig:DFS] ukazuje, jak DFS
funguje na příkladu.

Tato metoda je {\it úplná}, tj. pokud existuje řešení, pak bude vždy
nalezeno. Cenou za tento fakt je možnost expanze neúměrně velkého počtu
vrcholů.
\useexternalfigure
  [DFS][images/graph-dfs.pdf]
  [width=.8\textwidth]
\placefigure[here,force][fig:DFS]{DFS prochází postupně celou větev z~kořene stromu a pokud nenarazí na řešení provádí backtracking.}
{\externalfigure[DFS]}


\subsection[cp_lds]{Limited discrepancy search (LDS)}
Limited discrepancy search je v~constraint-based rozvrhování velmi
užívaným algoritmem. Jeho autoři se v~\cite[LDS]~zabývali vlastnostmi
heuristik a došli k~dvěma poznatkům, které zde uplatnili. 
\startitemize 
	\item Heuristika je méně spolehlivá na počátku prohledávání
(u~kořene stromu) než na konci.
	\item Dobrá heuristika chybuje málo. 
\stopitemize

Zavedli pojem \quotation{diskrepance}, který znamená právě jedno porušení
heuristiky.

Algoritmus LDS$(n)$\footnote{Pro řešení problému se může použít i více heuristik; pokud je jedna heuristika neúspěšná např. pro $n$ diskrepancí, pak se použije jiná pro $m <n$ počet diskrepancí. Je-li i ta neúspěšná, zvyšuje se dovolený počet diskrepancí a na řadě je opět původní heuristika.} postupuje podle heuristiky, ale může ji právě $n$-krát porušit. Porušení heuristiky provádí co nejdříve (kvůli první
		vlastnosti heuristiky).
Pokud nenajde řešení nastává backtracking, který probíhá až do
okamžiku, kdy pro zadané $n$ byly všechny větve prohledány. Pak se zvýší $n$ o~jedna a hledá znovu.
Průchod větvemi prohledávacího stromu ukazuje obrázek \in[fig:LDS].
%

\useexternalfigure
  [LDS][images/graph-lds.pdf]
  [width=.8\textwidth]
\placefigure[here,force][fig:LDS]{LDS prochází nejdříve větve s~nejmenším počtem
diskrepancí a upřednostňuje větve, kde je diskrepance blíže kořenu
	stromu.}
{\externalfigure[LDS]}


\subsection[cp_bab]{Branch and bound search (BAB)}
Algoritmus Branch and bound (větví a mezí) má za cíl najít optimální
řešení. V~podstatě pro svoji činnost využívá {\it uspořádané
	prohledávání}\footnote{Informovaná metoda prohledávání. Pracuje
		podobně jako DFS (podsekce \in[cp_dfs]). Rozdíl je
v~tom, že každý vrchol má svoje ohodnocení $g(i)$ a neexpanduje se první vrchol ze seznamu otevřených vrcholů, ale právě ten s~nejnižším ohodnocením $g(i)$.}. Díky němu najde řešení a pak se snaží nalézt řešení s~nižším ohodnocením (lepší). Přitom vyškrtne ze seznamu otevřených vrcholů všechny prvky, které mají ohodnocení vyšší než má nalezené řešení.
		
			Výhodou BAB oproti DFS je možnost přidávání
			podmínek za běhu a vlastnost, že najde vždy
			optimální řešení (pokud řešení existuje). Naopak nevýhodou oproti DFS je možná
			expanze vrcholů, které mají nízké ohodnocení,
			ale nevedou k~cíli. Ty jsou pak prohledávány
			zbytečně.
\section{CP v~rozvrhování}
Rozvrhovací problémy jako takové spadají do oblasti kombinatorických a
optimalizačních úloh (navíc mnohdy patří mezi NP-těžké)
a	tím pádem se dají dobře popsat omezujícími podmínkami (CSOP).


Nejdříve je nutné vytvořit model, kterým budeme reprezentovat jednotlivé
úlohy a stroje a relace mezi nimi. 

Úlohy jsou představovány jako proměnné s~danou doménou -- ta určuje
určitý časový okamžik. V~obecném případě modelujeme pro každou úlohu
$T_j \in {\cal T}$ tři proměnné. 
\startitemize
\item $start(T_j)$ : začátek vykonávání $s_j$
\item $end(T_j)$ : konec vykonávání $C_j$
\item $p(T_j)$ : doba vykonávání $p_j$
\stopitemize

Často se ale setkáváme s~případy, kdy je doba vykonávání $p_j$
konstantní a známá předem. Potom pro ni nemusíme vytvářet proměnnou stejně jako pro $C_j$, který se dá dopočítat. 

Podmínky, se kterými se často setkáváme:
\startitemize
	\item Vztah mezi začátkem a koncem vykonávání úlohy popsaný
	rovnicí\footnote{U nepreemptivního
		rozvrhování neplatí.} \in[eq:zaklad].
	\item Precedenční vazby jsou popsány vztahem \in[eq:precedence]
	\stopitemize
\placeformula
\startformula \startalign
\NC start(T_j)+p(T_j)\NC=end(T_j)\NR[eq:zaklad]
\NC end(T_i) \NC \leq start(T_j) \NR[eq:precedence]
\stopalign \stopformula	





Stroje se modelují proměnnou $processor(T_j)$ jen v~tehdy, když úlohy nemají
přiřazený stroj (dedicated processor), na kterém mají běžet. Pak tato
proměnná říká, na který stroj byla daná úloha rozvržena. 

Jsou-li $T_i$ a $T_j$ úlohy, které
mají běžet na stroji s~kapacitou 1, pak platí rovnice~\in[eq:kapacitaZdroje].
\placeformula[eq:kapacitaZdroje]
\startformula
 end(T_i) \leq start(T_j) \vee end(T_j) \leq start(T_i)
\stopformula
\subsection{Edge finding}
Velmi dobrým filtrovacím algoritmem v~rozvrhování s~omezujícími
podmínkami je \quotation{edge finding}. Jeho charakteristickou
vlastností je, že hledá precedenci mezi jednou úlohou a skupinou úloh. Z~toho
se pak dá usoudit, zda úloha bude provedena před nebo po skupině úloh. 

Mějme stroj s~jednotkovou kapacitou, úlohu $A$ a skupinu úloh
$\Omega\mbox{, }A \notin \Omega$. Potom $p(\Omega)$ značí celkový čas
potřebný k~vykonání všech úloh z~množiny $\Omega$.
\placeformula[eq:EF1]
\startformula
p(\Omega)=\sum_{X\in\Omega}p(X)
\stopformula
Předpokládejme dále, že úlohy z~$\Omega \cup \{A\}$ nezačínají úlohou $A$. Pak vykonávání úloh musí začít některou úlohou z~$\Omega$. Tím pádem nejmenší začátek vykonávání z~$\Omega$ je
\placeformula[eq:EF2]
\startformula
\min(start(\Omega)) = \min_{X \in \Omega}\{start(X)\}
\stopformula
Sečteme-li dobu vykonávání všech úloh s~nejmenším začátkem vykonávání a
porovnáme s~největším koncovým časem všech úloh, dojdeme k~závěru, že $A$ musí začínat dříve než jakákoliv úloha z~$\Omega$.
\placeformula[eq:EF3]
\startformula
\min(start(\Omega))+p(\Omega)+p(A) > \max(end(\Omega \cup \{A\}))
	\Rightarrow A<<\Omega
\stopformula
Podobně lze zjistit, že úloha $A$ bude následovat po všech úlohách
z~$\Omega$. Blíže o~tomto algoritmu v~\cite[Bartak_Introduction_CP,CBS].
\section[cp_gecode]{Knihovna Gecode}
	Gecode (\from[gecode-web]) je open-source knihovna podporující
	programování s~omezujícími podmínkami. Její výhodou je
	\quotation{otevřenost}, díky které si uživatel může připsat
	libovolný modul dle vlastních představ. Dalším jejím
	plusem jsou velmi dobré výsledky v~benchmark testech na rychlost
	řešení a paměťovou náročnost v~porovnání s~ostatními systémy
(\from[gecode-test]). Stále je ve vývoji a tedy hlavním problémem je
nedostatek dokumentace\footnote{dokumentace je pouze formou
	okomentovaných kódů	a několika vzorových programů}.
	
